
This application incorporates by reference Taiwanese application Serial No. 88112055, Filed Jul. 16, 1999.
1. Field of the Invention
The invention relates in general to a memory access in the Ethernet, and more particularly to an improved hashing scheme where the original entries in the multi-slot bucket are separated as entries and port masks in different location.
2. Description of the Related Art
Lookup of the forwarding table for destination medium access control (MAC) addresses is a basic operation in the Ethernet switch integrated circuit (IC). In the Ethernet, a server is provided with a switch hub for transmitting data among different hosts. A switch IC chip deposed in the switch hub connects the hosts according to the forwarding table. Conventionally, the forwarding table is established in a static random access memory (SRAM) in order to reduce system cost.
Referring to FIG. 1, a transmitter (computer) 10 is coupled to a port 12 of the switch hub 11 while a receiver (computer) 16 is connected to the switch hub 11 via a port 15. The data, forwarded from the transmitter 10, is received by a switch IC chip 14 of the switch hub II, and then passed on to the receiver 16.
In FIG. 1, the data of the transmitter 10 can be received by the receiver 16 because the MAC address of the receiver 16 is also sent out along with the data. The MAC address, including the address of the port 15 connected by the receiver 16, is received by the switch IC chip 14, and then transmitted to a SRAM 18 for the forwarding table lookup by a 128-bit data bus 17. Lookup for the forwarding table according to the MAC address decides the destination where the data is to be transmitted.
The size of the MAC address is 48 bits and the total number of computers in a local area network (LAN) usually comes to tens or hundreds. Conventionally, a hashing algorithm is employed to map the MAC address to a hash key for lookup of the forwarding table. The hash key is composed of 11 bits in the 48-bit MAC address so that the required memory is not costly.
However, owing to the fact that MAC addresses of different computers may have the same corresponding hash key, the above-mentioned hashing algorithm may result in a problem that the hash keys of different computers may conflict with each other. For example, an 11-bit hash key can correspond to 211 different MAC addresses in total. In a company, if there are 400 clients in the Ethernet, the probability that all hash keys are different with each other is (211xe2x88x921)/211xc3x97(211xe2x88x922)/ 211xc3x97(211xe2x88x923)/211xc3x97(211xe2x88x924)/211xc3x97. . . (211xe2x88x92397)/211xc3x97(211xe2x88x92398)/ 211xc3x97(211xe2x88x92399)/211≈0. That is to say, it is very possible that at least two of these hash keys are the same in this case.
In the prior art, a multi-slot bucket scheme is employed to reduce the probability of hash key conflict. The forwarding table is composed of continuous multi-slot buckets, each bucket corresponding to a unique hash key and having multi-slots to store individual forwarding table entries. Given a MAC address, a hash key can be derived and mapped to the corresponding multi-slot bucket.
The 4-slot bucket is taken for example as shown in FIG. 2. The lookup for the forwarding table is performed as follows. The hash key, derived from a given MAC address, is mapped to the corresponding kth 4-slot bucket. Then, the MAC address is used to compare with the first forwarding table entry (k, 0) of the kth 4-slot bucket. If the MAC field of this entry (k, 0) is not consistent with the content of the MAC address, the next entry (k, 1) will be tried again. The forwarding table entries (k, 2) and (k, 3) will be tried successively if the former entries (k, 0) and (k, 1) are not identical with the MAC address. Therefore, there are up to 4 tries for a lookup. In practice, the probability of lookup miss will be very small. However, it requires four table entry accesses to SRAM in the worst case.
The memory space and the access time are usually considered to be the most important aspects in the IC design. Therefore, if the memory space used for lookup of the forwarding table and the access time of memory can be effectively reduced, the efficiency of the conventional hashing algorithm can be greatly improved.
It is therefore an object of the invention to provide a method for performing a MAC address lookup in a network switch to enable data transmission to a network node associated with the MAC address in an Ethernet network. This method is an improved hashing scheme in the Ethernet where the rarely used field is separated from each forwarding table entry so that memory space can be saved for storing more forwarding table entries, and thus the access time of memory can be effectively reduced.
The invention achieves the above-identified objects by providing a memory structure in the Ethernet. The memory structure includes a plurality of multi-slot buckets. Each of the multi-slot buckets is mapped to a hash key that is formed by partial bits in a MAC address. Besides, each of the multi-slot buckets has a number of forwarding table sections, each storing a number of forwarding table entries. If two forwarding table entries are stored and read by a burst read mode in each forwarding table section of a 4-slot bucket, xc2xc memory space and xc2xd access time can be saved.
The invention achieves another object by providing a memory access method. First, a hash key of a MAC address is mapped to a multi-slot bucket of a forwarding table in a memory. Then, a number of forwarding table entries are read from a forwarding table section of the multi-slot bucket by a burst read mode. If two forwarding table entries are stored in each forwarding table section of a 4-slot bucket, xc2xc memory space and xc2xd access time can be saved. Thus, the lookup for the forwarding table according to the MAC address in the Ethernet switch IC can be effectively performed.